Golang вопросы собеседований

👣 Задача: 395. Самая длинная подстрока, содержащая не менее K повторяющихся символов

В этой задаче Вам необходимо найти самую длинную подстроку строки \(s\), такую что каждая буква в ней встречается не менее \(k\) раз.

Если такой подстроки нет, вернуть 0.

Пример:

Вход: s = "aaabb", k = 3
Выход: 3

Объяснение: Самая длинная подходящая подстрока – "aaa", так как буква 'a' повторяется три раза.
### Описание алгоритма:

1. Генерация подстрок: Генерируем все возможные подстроки строки \(s\). Для каждой подстроки будем отслеживать частоту появления символов при помощи массива countMap.

2. Проверка валидности: Метод isValid проверяет, что каждый символ в текущей подстроке появляется хотя бы \(k\) раз. Это делается через проверку значений в массиве countMap. Если все символы удовлетворяют условию, то подстрока считается допустимой.

3. Обновление результата: Отслеживаем максимальную длину допустимых подстрок. Когда находим новую подходящую подстроку большей длины, обновляем результат. В итоге возвращаем длину самой длинной найденной подстроки.
Ответ:

package main

import (
    "fmt"
)

func longestSubstring(s string, k int) int {
    if len(s) == 0 || k > len(s) {
        return 0
    }
    n := len(s)
    result := 0

    for start := 0; start < n; start++ {
        countMap := make([]int, 26)
        for end := start; end < n; end++ {
            countMap[s[end]-'a']++
            if isValid(countMap, k) {
                if end-start+1 > result {
                    result = end - start + 1
                }
            }
        }
    }
    return result
}
func isValid(countMap []int, k int) bool {
    countLetters, countAtLeastK := 0, 0
    for _, count := range countMap {
        if count > 0 {
            countLetters++
        }
        if count >= k {
            countAtLeastK++
        }
    }
    return countLetters == countAtLeastK
}

func main() {
    fmt.Println(longestSubstring("aaabb", 3)) // Output: 3
    fmt.Println(longestSubstring("ababbc", 2)) // Output: 5
}

@golang_interview

Please open Telegram to view this post

VIEW IN TELEGRAM

www.tg-me.com/in/Golang вопросы собеседований/com.golang_interview/1026

5.0K viewsedited  Nov 25, 2024 at 07:55

👣 Задача: 395. Самая длинная подстрока, содержащая не менее K повторяющихся символов

В этой задаче Вам необходимо найти самую длинную подстроку строки \(s\), такую что каждая буква в ней встречается не менее \(k\) раз.

Если такой подстроки нет, вернуть 0.

Пример:

Вход: s = "aaabb", k = 3
Выход: 3

package main

import (
    "fmt"
)

func longestSubstring(s string, k int) int {
    if len(s) == 0 || k > len(s) {
        return 0
    }
    n := len(s)
    result := 0

    for start := 0; start < n; start++ {
        countMap := make([]int, 26)
        for end := start; end < n; end++ {
            countMap[s[end]-'a']++
            if isValid(countMap, k) {
                if end-start+1 > result {
                    result = end - start + 1
                }
            }
        }
    }
    return result
}
func isValid(countMap []int, k int) bool {
    countLetters, countAtLeastK := 0, 0
    for _, count := range countMap {
        if count > 0 {
            countLetters++
        }
        if count >= k {
            countAtLeastK++
        }
    }
    return countLetters == countAtLeastK
}

func main() {
    fmt.Println(longestSubstring("aaabb", 3)) // Output: 3
    fmt.Println(longestSubstring("ababbc", 2)) // Output: 5
}